package leetcode.editor.cn;

public class _338_CountingBits {
    public static void main(String[] args) {
        Solution solution = new _338_CountingBits().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    // 最低设置位
    // 定义正整数 x 的「最低设置位」为 x 的二进制表示中的最低的 1 所在位
    class Solution {
        public int[] countBits(int num) {
            int[] res = new int[num + 1];
            for (int i = 1; i <= num; i++) {
                res[i] = res[i & (i - 1)] + 1;
            }
            return res;
        }
    }

    // 最低有效位
    class Solution2 {
        public int[] countBits(int num) {
            int[] res = new int[num + 1];
            for (int i = 1; i <= num; i++) {
                res[i] = res[i >> 1] + (i & 1);
            }
            return res;
        }
    }

    // 最高有效位
    class Solution3 {
        public int[] countBits(int num) {
            int[] res = new int[num + 1];
            int highBit = 0;
            for (int i = 1; i <= num; i++) {
                if ((i & (i - 1)) == 0) {
                    highBit = i;
                }
                res[i] = res[i - highBit] + 1;
            }
            return res;
        }
    }


    // 笨方法
    class Solution4 {
        private int numOfOne(int n) {
            int res = 0;
            while (n != 0) {
                res++;
                n &= (n - 1);
            }
            return res;
        }

        public int[] countBits(int num) {
            int[] res = new int[num + 1];
            for (int i = 0; i <= num; i++) {
                res[i] = numOfOne(i);
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}